package LC;

import java.util.Arrays;

/**
 * https://leetcode.com/problems/maximum-gap/description/
 * Given an unsorted array, find the maximum difference between the successive elements in its sorted form.
 * Try to solve it in linear time/space.
 * Return 0 if the array contains less than 2 elements.
 * You may assume all elements in the array are non-negative integers and fit in the 32-bit signed integer range.
 * Credits:
 * Special thanks to @porker2008 for adding this problem and creating all test cases.
 */
public class LC_164_MaximumGap_BucketSort_Greedy {
    public static void main(String[] args) {
        System.out.println(Solution.maximumGap(new int[]{1, 2, 100, 3, 4}));
    }

    static class Solution {
        static int maximumGap(int[] nums) {
            if (nums == null || nums.length < 2) return 0;
            int len = nums.length;
            int max = nums[0], min = nums[0];
            for (int num1 : nums) {
                max = Math.max(max, num1);
                min = Math.min(min, num1);
            }
            //Math.ceil与最小的比这个数大的蒸熟，使bucket可以包含所有数
            int gap = (int) Math.ceil((double) (max - min) / (len - 1));
            int[] BucketsMIN = new int[len - 1];
            int[] BucketsMAX = new int[len - 1];
            Arrays.fill(BucketsMIN, Integer.MAX_VALUE);
            Arrays.fill(BucketsMAX, Integer.MIN_VALUE);
            for (int num : nums) {
                //不考虑边界，所以把边界的min和max都拿出来，单独再考虑
                if (num == min || num == max) continue;
                int bucket = (num - min) / gap;
                BucketsMIN[bucket] = Math.min(BucketsMIN[bucket], num);
                BucketsMAX[bucket] = Math.max(BucketsMAX[bucket], num);
            }
            int result = 0;
            int previous = min;
            for (int i = 0; i < len - 1; i++) {
                if (BucketsMIN[i] == Integer.MAX_VALUE && BucketsMAX[i] == Integer.MIN_VALUE) continue;
                result = Math.max(result, BucketsMIN[i] - previous);
                previous = BucketsMAX[i];
            }
            result = Math.max(result, max - previous);
            return result;
        }
    }
}